The invention relates to a method for traversing a partition tree in the direction of a semi-infinite straight-line and to an image processor for implementing the method. In particular, the present invention relates to a method for the computer-supported image generation, whereby there is tracked the path of individual rays (ray tracing).
During ray tracing, this relates to a known method to be able to compute three-dimensional views of an object or a scene in that the ray path of the light beams which strike on the image plane are computed pixel by pixel. For more complex ray tracing methods, not only are the rays considered which when emanating from the objects strike against the image plane, but also those rays are considered which illuminate the object or, respectively the scene (secondary rays, tertiary rays). With the aid of such types of complex ray tracing processes, there can be generated three-dimensional views of objects of a high quality; through a consideration of secondary rays it is in particular possible to also consider reflections and illumination effects.
The disadvantage of all ray tracing methods; however relates to the extreme high demand on computation, which renders the method extremely time consuming. With regard to every light beam there must be computed as to whether and when at which location there is effected the striking against a specified three-dimensional surface structure. When there should also be considered additionally secondary rays, then the demand for computational output becomes immense.
There have been proposed different methods for accelerating the ray path computation. As a rule, the rays must pass through large volumes of open spatial regions prior to an eventual impact against a surface of the object which is to be represented, and in which regions no surface structures are located. Due to this reason, there can be precluded any collision of a ray with a surface for these open spatial regions. Due to this reason it has been attempted to detect these open spatial volumes most skillfully and flatly as so to preclude from any consideration collisions between rays and surfaces. Also there must be considered that the objects which are to be represented should be packaged most skillfully in a fitting encompassing volume, and to implement only within the encompassing volume a collision of ray-surface.
It is known to encompass the different objects which are to be represented with spherical hemispheres or shells. In order to determine into which hemispherical shell the ray then enters, there are however required the implementing distance computations which, for spherical surfaces, necessitate a considerable amount of computing time. It is more advantageous to utilize cubic or, respectively parallelepiped encompassing volumes. For example, the scene which is to be represented can have a cubic grid superimposed thereon, whereby for every cube element there must be provided a memory storage as to whether it does or does not contain a surface structure. However, this leads to an increase in demand for memory storage to the third power for the side length of the encompassing spatial region. A large surfaced, empty spatial region must during this method be represented by a multiplicity of empty cube elements, whereby for every cube element there must be individually interrogated as to whether it is also actually empty. It would be better, however, with regard to a large-surfaced empty spatial region to be able to determine by means of a single interrogating step that the latter does not contain any structures.
For this purpose there are known adaptive spatial partitions, in which a spatial volume is divided in dependence upon local conditions into larger volume or smaller volume cubes. For the two-dimensional case, this method of surface partition is known under the name xe2x80x9cquadtreexe2x80x9d, while here every quadrate is divided in accordance with need into four subsidiary quadrates. Such a quadrate partition is represented in FIG. 2.
In the three-dimensional case, a certain spatial cube is divided, as needed, into eight sub-cubes. For the three-dimensional case, the method of the adaptive spatial partition is known under the name xe2x80x9coctreexe2x80x9d. FIG. 5A illustrates such type of an octree partition.
For the purpose of ray tracing there is afforded the utilization of such types of adaptive spatial partitions. In all instances, one must be able to compute which of the different cubes are to be traversed by a semi-infinite straight line or ray consecutively.
Accordingly, it is an object of the invention, to render available for the ray-based image generation (ray tracing) a rapid, computer-supported method for traversing a space partition in the direction of a semi-infinite straight line or ray, which in succession delivers the terminal cells of the space partition which are traversed by the rays. Furthermore, it is an object of the invention to make available an image processor for implementation of the inventive method, which enables the terminal cells of the space partition which are traversed by the rays to be detected at a high rate of speed.
The object of the invention is solved by means of a method for traversing a partition tree in the direction of a ray pursuant to claim 1 and claim 22, as well as through an image processor pursuant to claim 27.
Pursuant to the inventive method there are in succession determined the terminal cells of the space partition which are traversed by a ray. For this purpose, the intersecting point of the successive terminal cell is determined with the aid of a sequence of decrements. In order to determine the intersecting point it is accordingly not necessary to have to perform an intersection computation which would necessitate time consuming division operations. Instead thereof, the intersecting point is determined by a small number of decrementing steps. For the implementation of every decrementing step there are exclusively required integer operations. As a result, the method can be implemented very rapidly by means of a computer or an image processor.
Every decrement of the utilized sequence of decrements is effected by a halving from the preceding decrement. The decrements of the sequence are consequently in a ratio of powers of two. This determination of the decrements corresponds to a xe2x80x9cbinary searchxe2x80x9d, the intersecting point can be attained in this manner with the lowest possible number of decrementing steps. This determination of the decrements represents an optimization of the operational speed.
As to whether the terminating conditions is fulfilled, can be simply tested by a computer or image processor. It must be merely interrogated as to whether the respective decremented distance is zero or not. This testing can be implemented at a rapid speed.
The inventive method is particular optimized for the utilization in computers and processors, and achieves therein a heretofore not possible processing speed during image generation by means of ray tracing. The individual rays during a ray tracing method can be tracked by means of the inventive method at a previously unknown rapidity. In particular, by means of the inventive method it is possible to completely preclude large spatial regions which are penetrated by the semi-infinite straight-lines or rays from a collision testing between rays and surfaces.
It is advantageous when step (e) is only implemented during the first traversal. The computation of the decrements for each semi-infinite straight-line or ray need be effected precisely only a single time. For determining the individual terminal cells which are traversed by the ray there can always again be reached back to the singly determined decrements.
It is also of advantage when step (e) is not implemented between (d) and (f), but at a suitable location prior to step (d). The different decrements can also be previously determined for a specified semi-infinite straight-line.
Pursuant to a further advantageous embodiment of the invention, the components of the directional vector are so permutated prior to beginning of the method, so that the x-components become the main components, in essence, the relatively largest components. The method is thereby applicable for suitable directional vectors also when for these directional vectors, initially the y-components or the z-components were the relatively largest components of the vector.
It is advantageous when, with regard to the terminal cell determined in step (c), it is tested as to whether this relates to a structure filled cell or to an empty cell. For the instance, in which it relates to an empty cell, there does not have to be implemented any collision computation between rays and surfaces for this cell. This enables large surfaced or, respectively spatial regions to be previously precluded from the collision consideration.
For the case in which the terminal cell is a structure-filled cell, with regard to this cell there is determined as to whether the semi-infinite straight-line or ray collides with the therein contained structure. In this instance, there must thus be implemented the collision computation between rays and surfaces. This collision computation can have two possible results: either the ray strikes the therein contained objects, or the ray misses the objects. In the case in which the ray misses the objects, it traverses the space partition further, and to that extent, the next terminal cells which are traversed by the ray must be determined. At the presence of a collision of the semi-infinite straight-line with the structure contained in the terminal cell, the method is completed in that regard.
It is of advantage when during decrementing which is repeated in step (f), the main components as well as also the secondary components of collective distances determined in step (d) there is began with the decrement xe2x80x9cedge length of the encompassing terminal cellxe2x80x9d in the main components. In this manner, during repeated decrementing the first decrements can be skipped over. This leads to an additional time saving, and the method consequently becomes more rapid.
It is of advantage when the initial offset which belongs to the starting point is determined through the setting to zero the initial offset of the main components, as well as through the computing of the associated initial offset of the secondary components. In this manner there is achieved with respect to the main components there can be computed in integers or in whole numbers. After-decimal point or fractional integer locations consequently need not be considered with regard to the main components. Also, there is achieved thereby a further acceleration of the method. In order to. determine the terminal cell of the space partition which encompasses a specified unit cell, there is applied the method pursuant to claim 12. Through a columnar readout of the line-wise arranged binary coordinates of the impact point of the unit cell, there can be extremely rapidly determined the indices for the applicable sub-tree.
This advantage when the starting points given in a suitable original coordinate system recalculated by means of the factor g=2maximum depth/r into the coordinate system of the partitioned region with the side length 2maximum depth, whereby r represents the maximum expanse of the original coordinate system. With the aid of scaling at the factor g, a transition can be formed from a suitable coordinate system into a coordinate system with the side length 2maximum depth. For the case in which the original coordinate system also encompasses negative coordinate values, it is initially displaced through a translation into the non-negative coordinate range. Mostly, there is utilized a Cartesian coordinate system. However, other suitable vector spaces can be utilized which are plotted through linearly independent base vectors, whereby the base vectors need not necessarily be orthogonal.
The inventive image processor for implementing the method compasses means for determining the distances from the walls of the encompassing terminal cell, means for decrementing said collective specified distances, means for determining the contiguous unit cell, and means for determining that terminal cell which encompasses said contiguous unit cell. The decrements can be computed prior to or during the implementation of the method. As soon as these decrements are present, the method can be implemented at a high rate of speed.
It is advantageous when the whole numbered portions of the decrements in the subsidiary directions are represented as integer numbers. It is furthermore of advantage when the fractional value portions of the decrements in the subsidiary directions are represented as integer numbers. Furthermore it is of advantage when the initial offsets are represented as integer numbers. Integer numbers can be processed by the image processor at a high speed. Also, fractional or decimal fractional numbers can be represented through integer numbers, in which the range from 0 to 1 is formed on the corresponding region by integers or whole numbers. In accordance with the amount of bits which the integer number encompasses, there can be adjusted the accuracy to the present need.
Pursuant to an advantageous embodiment of the invention, the entire sequence of the decrements of the main components as well as of the associate decrements of the secondary components are produced by means of slide registers. This has the advantage for the readout of the different decrements, a single readout port is adequate, through which there can be successively read out the entire sequence of the decrements.
Alternatively thereto, it is possible to produce the entire sequence of the decrements of the main component as well as of the associated decrements of the secondary components by means of a multiplicity of readout ports which are each offset relative to each other by one bit. In this manner, collective decrements are immediately available, which is of particular advantage for the parallelization of the method.
It is also advantageous when the image processor for implementing the inventive method compasses an array in which the binary representations of the n truncated coordinate bits of a point of the unit cell are stored. By means of that type of array there can be simply implemented a columnar readout of the truncated coordinates.